1. Field of the Invention
The present invention generally relates to the fabrication and design of semiconductor chips and integrated circuits, and more specifically to a method of evaluating computer-aided design (CAD) tools used in mapping the physical layout and wiring of logic cells in an integrated circuit.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements grouped to perform a logic function. Cells types include, for example, core cells, scan cells and input/output (I/O) cells. Each of the cells of an IC may have one or more pins, each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for routing, such as a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are all used for vertical and/or horizontal routing.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins. An electronic design automation (EDA) system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.), and translates this high level design language description into netlists of various levels of abstraction. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The result is a set of design files known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps.
The process of converting the specifications of an electrical circuit into the arrangement which is formed on the chip is called the physical design, which includes both the layout (placement) and wiring (routing) of cells. Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of a integrated circuit device. Due to the large number of components and the details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
Placement algorithms are typically based on either a simulated annealing, cut-based partitioning, or analytical paradigm (or some combination thereof). Recent years have seen the emergence of several new academic placement tools, especially in the top-down partitioning and analytical domains. The advent of multilevel partitioning as a fast and extremely effective algorithm for min-cut partitioning has helped spawn a new generation of top-down cut-based placers. A placer in this class partitions the cells into either two (bisection) or four (quadrisection) regions of the chip, then recursively partitions each region until a global coarse placement is achieved. Such recursive cut-based placement can perform quite well when designs are dense, but they perform rather poorly when the designs are sparse. Sparse designs tend to fool the partitioner since it does not know how to handle the large flexibility in the balance tolerance.
Simulated annealing approaches try making moves of randomly chosen cells and accepting each move based on a probabilistic function. Annealing typically produces excellent results though it requires high runtime.
Analytical placers typically solve a relaxed placement formulation (such as minimizing total quadratic wirelength) optimally, based on relaxed constraints which allow cells to temporarily overlap. Legalization is achieved by removing overlaps via either partitioning or by introducing additional forces and/or constraints to generate a new optimization problem. The classic analytical placers, PROUD and GORDIAN, both iteratively use bipartitioning techniques to remove overlaps.
FIGS. 1A–1C illustrate a typical placement process according to the prior art. First, a plurality of the logic cells 2 are placed using the entire available region of the IC 4 as shown in FIG. 1A. After initial placement, the chip is partitioned, in this case, via quadrisection, to create four new regions. At the beginning of the partitioning phase some cells may overlap the partition boundaries as seen in FIG. 1B. The cell locations are then readjusted to assign each cell to a given region as shown in FIG. 1C. The process then repeats iteratively for each region, until the number of cells in a given region reaches some preassigned value, e.g., one. While FIGS. 1A–1C illustrate the placement of only seven cells, the number of cells in a typical IC can be in the hundreds of thousands, and there may be dozens of iterations of placement and partitioning.
Placement helps to identify needed changes in the logic, required buffering, gate sizing, routing congestion, etc. Once these problems are fixed, the placement process may have to be run again on the adjusted design. Ideally, after each subsequent placement run, the problems that were fixed the last time stay fixed, and new problems do not crop up. To achieve timing closure, one often has to run through several iterations of physical synthesis flows, for which placement is a critical step. During these iterations, one hopes to consistently move towards design convergence. However, if a placement algorithm returns a radically different solution than it did the previous time, entirely new problems could emerge.
It is thus paramount that a placement algorithm not only return a high quality solution, but also be stable, returning similar solutions even for slightly different inputs and/or constraints. The stability of the algorithm is arguably as important a characteristic as the wirelength it achieves. However, there is currently no way to quantify the stability of a placement algorithm. It would, therefore, be desirable to devise metrics that measure the stability of a placement algorithm. It would be further advantageous if the metrics could convincingly illustrate that some algorithms are quantifiably more stable than others in terms of their effectiveness for achieving timing closure.